package com.easy.leetcode.dp;

//583. 两个字符串的删除操作
public class MinDistance {
    /**
     * 最大最小 ，动态规划
     *
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        //定义状态转移方程，dp 表示word1长度为i,word2长度为j时，最长公共字符串
        //注意，此处我们定义的dp 数组是针对字符串的长度的，所以创建数组时需m+1,n+1;
        int[][] dp = new int[m + 1][n + 1];
        //当i为0或者j为0时，最长公共字符串为0
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                //i j分别表示两个字符串长度，对应的索引应该减1
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        //dp[m][n] 表示最长公共字符串
        //删除的字符长度为两个字符串的和减2倍的最长公共字符串长度
        return m + n - 2 * dp[m][n];
    }
}
